package algorithm_demo.demo02;
import java.util.Stack;
/**
 * 二叉树，非递归方式，利用栈实现

 * @author Api
 * @date 2023/2/7 21:12
 */
public class Code01_BinaryTreeTraversal {

    public static class TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;
    }
    //先序遍历非递归
    //  规则：
    //  1. 弹出即打印
    //  2. 如有右节点，压入右节点
    //  3. 如有左节点，压入左节点
    public static void pre(TreeNode head){
        System.out.println("pre-order: ");
        if (head != null){
            Stack<TreeNode> stack = new Stack<>();
            //压入头节点
            stack.add(head);
            while(!stack.isEmpty()){
                //弹出元素
                head = stack.pop();
                System.out.println(head.value+" ");
                //优先判断：右节点不为null，压入右节点
                if (head.right != null){
                    stack.push(head.right);
                }
                //其次：左节点不为null，压入左节点
                if (head.left != null){
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    //后序非递归
    public static void pos(TreeNode head){
        System.out.println("pos-order: ");
        if (head != null){
            Stack<TreeNode> s1 = new Stack<TreeNode>();
            Stack<TreeNode> s2 = new Stack<TreeNode>();
            s1.push(head);
            while(!s1.isEmpty()){
                head = s1.pop();
                s2.push(head);
                if (head.left != null){
                    s1.push(head.left);
                }
                if (head.right != null){
                    s1.push(head.right);
                }
            }
            while(!s2.isEmpty()){
                System.out.println(s2.pop().value+" ");
            }
        }
        System.out.println();
    }


    //中序遍历，非递归
    //1. 整条左边界依次入栈
    //2. 当我第一条逻辑无法命中时，则弹出节点并打印，然后来到右树上继续执行第一条规则
    public static void in(TreeNode head){
        System.out.println("in-order: ");
        if (head != null){
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while(!stack.isEmpty() || head != null){
                if (head != null){
                    stack.push(head);
                    head = head.left;
                }else{
                    head = stack.pop();
                    System.out.println(head.value+" ");
                    head = head.right;
                }
            }
        }
        System.out.println();
    }




}
